package com.example.algorithm.huawei_rongyao_29;
import java.util.Scanner;

// 排成一条线的纸牌博弈问题

/**
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌.
 * 规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左和最右的纸牌，玩家A和玩家B绝顶聪明。请返回最后的获胜者的分数。
 * 输入描述:
 * 输出包括两行，第一行一个整数n，代表数组arr长度，第二行包含n个整数，第i个代表arr[i]。
 * 输出描述:
 * 输出一个整数，代表最后获胜者的分数。
 *
 * 这段代码是一个经典的二维动态规划问题，用于解决一个关于“拿石子游戏”的问题。
 * 具体来说，给定一个数组 arr，其中每个元素代表一堆石子的数量，两个人轮流从数组的两端取石子，目标是拿到最多的石子。
 * win2 函数计算在最优策略下，第一个取石子的玩家能拿到的最多石子数。让我们逐句解析代码。
 * 这段代码通过动态规划的思想，使用两个二维数组 f 和 s 来记录子问题的解，最终计算出在最优策略下，第一个玩家能拿到的最多石子数。
 */
public class Q07_CardGameWinner {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int winnerScore = maxScore(arr);
        System.out.println(winnerScore);
        scanner.close();
    }

    public static int maxScore(int[] arr) {
        // 检查数组是否为空或长度为零
        if (arr == null || arr.length == 0) {
            return 0; // 返回0表示没有卡片可拿
        }

        // 创建两个二维数组 f 和 s，用于动态规划
        // f与s目前均是一个n*n的二维数组。空的。
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];

        // 遍历数组 arr，初始化对角线上的值。是捺对角线
        // 在对角线 f[j][j] 处，表示只剩一个元素时，第一个玩家能拿到的石子数就是这个元素本身。
        for (int j = 0; j < arr.length; j++) {
            f[j][j] = arr[j]; // 当只有一个元素时，第一个玩家只能拿这个元素???
            // 似乎少了下面这句。后续加上了再试试。
            //s[j][j] = arr[j];

            // 逆向遍历，处理所有子问题
            // 下面的动作是在：填充动态规划表
            // 通过逆向遍历，处理所有子数组范围 [i, j] 的子问题：
            //f[i][j] 计算在第一个玩家选择 arr[i] 或 arr[j] 后的最优结果：
            //如果第一个玩家选择 arr[i]，则第二个玩家将在 [i+1, j] 范围内拿石子，所以第一个玩家最终能拿到的石子数是 arr[i] + s[i+1][j]。
            //如果第一个玩家选择 arr[j]，则第二个玩家将在 [i, j-1] 范围内拿石子，所以第一个玩家最终能拿到的石子数是 arr[j] + s[i][j-1]。
            //s[i][j] 计算在第二个玩家面对 arr[i] 到 arr[j] 范围时，第一个玩家之后能拿到的最少石子数：
            //第二个玩家选择使得第一个玩家在之后的选择中拿到的石子数最小。所以取 f[i+1][j] 和 f[i][j-1] 中的最小值。
            for (int i = j - 1; i >= 0; i--) {
                // f[i][j] 表示在数组 arr 的 i 到 j 范围内，第一个玩家能拿到的最多石子数
                // f[i][j]表示arr[i...j]段，被绝顶聪明的人先拿获得的分数
                // arr[i] + s[i + 1][j]表示的是，当前轮如果它是先手，如果他先手拿arr[i]，那么，他的下一次，是相当于是拿arr[i+1...j]段的后手，也就是s[i + 1][j]。
                // arr[j] + s[i][j - 1]表示的是，当前轮如果它是先手，如果他先手拿arr[j]，那么，他的下一次，是相当于拿arr[i...j-1]段的后手，也就是s[i][j - 1]。
                // 我们现在是在给f[i][j]赋值。也就是要确定它。那么，一个聪明绝顶的人，面对arr[i...j]的数组，???
                // 之所以两中情况取max，是因为，站在自己是先手的角度，肯定是希望，自己拿的越大越好。
                f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
                // s[i][j] 表示在数组 arr 的 i 到 j 范围内，第二个玩家能拿到的最多石子数
                // s[i][j]表示arr[i...j]段，被绝顶聪明的人后拿获得的分数
                // 先拿的人可能拿走arr[i]或arr[j]。因为先拿的也是绝顶聪明，因此函数返回min(f[i+1][j], f[i][j-1])
                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
            }
        }

        // 返回第一个玩家在整个数组范围 [0, arr.length - 1] 内能拿到的最多石子数，这取决于 f[0][arr.length - 1] 和 s[0][arr.length - 1] 的最大值。
        // 返回在最优策略下，第一个玩家能拿到的最多石子数
        // 虽然是玩家A先拿。但是题目说的是返回最后获胜玩家的分数。是A或者B是不确定的。事实上，胜者可能是A，也可能是B，这和给的数组有关。
        // 所以，我们这里加了个max，然后比较f和s最右上角的那个值。
        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
    }
}

